package frist50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T0018 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int first = 0; first < len; first++) {
            if (first > 0 && nums[first] == nums[first - 1]) continue;
            for (int second = first + 1; second < len; second++) {
                if (second > first + 1 && nums[second] == nums[second - 1]) continue;
                int four = len - 1;
                long targetS = (long)target - nums[first] - nums[second];
                for (int third = second + 1; third < len; third++) {
                    if (third > second + 1 && nums[third] == nums[third - 1]) continue;
                    while (third < four &&nums[third]+nums[four]>targetS)four--;
                    if (third==four)break;
                    if (nums[third]+nums[four]==targetS){
                        List<Integer> tmp=new ArrayList<>();
                        tmp.add(nums[first]);
                        tmp.add(nums[second]);
                        tmp.add(nums[third]);
                        tmp.add(nums[four]);
                        list.add(tmp);
                    }
                }
            }
        }
        return list;
    }
}
